package com.mlh.greed;

/**
 * @author 缪林辉
 * @date 2024/4/9 13:54
 * @DESCRIPTION
 */
// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组是数组中的一个连续部分。
// 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
// 输出：6
// 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
public class 最大子数组和 {
    //贪心策略：只要子数组之和<0，就寻找新的开始
    //否则就继续相加
    //可以将子数组看作一个数 子数组后一个元素看作一个数
    // 无非有4中情况  正 正 ；正 负；负 负；负 正
    //其他情况都很好判断  难一点的就是这个 正 负
    //只要这个正+负不为负，就是值得的，他会让下一个正数增大而不是变小
    //代码随想录总结：
    // 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
    // 全局最优：选取最大“连续和”
    //不论是新的开始 还是进行相加  都去和max进行比较  更新max
    public int method1(int[] nums) {
        int total=0,max=Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(total<0){
               total=nums[i];
            }else {
                total+=nums[i];
            }
            max=total>max?total:max;
        }
        return max;
    }
}
